package com.scqzy.shengchunqiang.sword2offer.day15;

import com.scqzy.shengchunqiang.structure.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;

/**
 * @Description: 剑指 Offer 54. 二叉搜索树的第k大节点
 * @Author 盛春强
 * @Date 2021/8/23 0:23
 */
public class KthLargest {

    public int kthLargest(TreeNode root, int k) {
        int c = 0;
        Deque<TreeNode> deque = new ArrayDeque<>();
        while (Objects.nonNull(root) || !deque.isEmpty()) {
            while (Objects.nonNull(root)) {
                deque.push(root);
                root = root.right;
            }
            if (++c == k) {
                return deque.peek().val;
            }
            root = deque.pop().left;
        }
        return 0;
    }

    int c;
    int k;
    int res;
    public int kthLargest1(TreeNode root, int k) {
        this.c = 0;
        this.k = k;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if (Objects.isNull(root) || c == k) {
            return;
        }
        dfs(root.right);
        if (++c == k) {
            res = root.val;
            return;
        }
        dfs(root.left);
    }
}
